/***************************************************
 * intro111/ipis111: Third assignment              *
 *                                                 *
 * This class is for assignment #3 - Part 2        *
 *                                                 *
 * Author(s): ### YOUR NAME(S) AND EMAIL(S). ##### *
 * Date: ##/##/####                                *
 *                                                 *
 ***************************************************/

/*
 * Important! Add comments to every method!
 *
 * The "return" statement at the end of each method and the initial value 
 * is just so this skeleton file compiles, change it according to your needs
 */

public class Ex2 {

	public static double distance(int[] point1, int[] point2) {
		return Math.sqrt(Math.pow(point1[0] - point2[0], 2)
				+ Math.pow(point1[1] - point2[1], 2));
	}

	public static boolean lexGreaterThan(int[] p1, int[] p2) {
		return (p1[0] > p2[0]) || (p1[0] == p2[0] && p1[1] > p2[1]);
	}

	/******************** Task 1 ********************/
	public static int[][] findClosestSimple(int[][] points) {
		int[][] res = null;
		if(points.length==2)//no need to check for 2 points
			return points;
		
		
		if(points.length>1)
		{
			double temp;
			double min=distance(points[0],points[1]); //get some initial distance to compare with
			res=new int[2][2];//initialize the result array
			res[0]=points[0];
			res[1]=points[1];
			for(int i=0;i<points.length;i++)//loop through the points list
			{
				for(int j=i+1;j<points.length;j++)//loop through the rest of the points to make sure we test each pair only once
				{
					temp = distance(points[i],points[j]);
					if (min>temp)//compares to current shortest distance
					{
						min=temp;
						res[0]=points[i];
						res[1]=points[j];
					}
				}
			}
		}
		return res;
	}

	/******************** Task 2 ********************/
	public static int[][] firstHalf(int[][] points)
	{
		if(points.length<=1)
		{
			return points;
		}
		else
		{
			int mid=(points.length/2);
			int[][] ans = new int[mid][2];
			for(int i=0;i<ans.length;i++)
			{
				ans[i]=points[i];
			}
			return ans;
		}
		
	}
	public static int[][] secondHalf(int[][] points)
	{
		if(points.length<=1)//dont split single cell array
		{
			return points;
		}
		else
		{
			int mid=(points.length-(points.length/2));//calculate array middle point
			int[][] ans = new int[mid][2];
			for(int i=points.length/2;i<points.length;i++)//loop through points from mid point to end
			{
				ans[i-points.length/2]=points[i];//populate result array
			}
			return ans;
		}
		
	}
	public static int[][] sortByLex(int[][] points) {
		int[][] ans = new int[points.length][2];
		
		
		if (points.length<=1)
		{
			return points;
		}	
		ans=merge(sortByLex(firstHalf(points)),sortByLex(secondHalf(points)));
		return ans;	
	}
		
	
	public static int[][] merge(int[][] points1,int[][] points2) {
		int i=0;
		int j=0;
		int k=0;
		int[][] ans = new int[points1.length+points2.length][2];
		while(i<points1.length || j<points2.length)
		{
			if(i<points1.length && j<points2.length)
			{
				if(lexGreaterThan(points1[i],points2[j]) )
				{
					ans[k]=points2[j];
					k=k+1;
					j=j+1;
				}
				else
				{
					ans[k]=points1[i];
					k=k+1;
					i=i+1;
				}
			}
			else
			{
				if(i<points1.length)
				{
					ans[k]=points1[i];
					k=k+1;
					i=i+1;
				}
				else
				{
					ans[k]=points2[j];
					k=k+1;
					j=j+1;
				}
			}
		}
		
			
		return ans;	
	}
		
	

	public static int[][] flip(int [][] points)
	{
		int[][]ans =new int[points.length][2];
		for(int i=0;i<points.length;i++)
		{
			
			ans[i][0]=points[i][1];
			ans[i][1]=points[i][0];
		}
		return ans;
	}
	public static int[][] sortByY(int[][] points) {
		int[][] ans = new int[points.length][2];
		ans=sortByLex(flip(points));//flip coordinate order and then run lexsort;
		return flip(ans);//flip coordinates again to return to normal order;
	}

	public static int[] duplicates(int[][] points) {
		int[] res = null;
		for(int i=0;i<points.length-1;i++)//loop through the array once since it is sorted
		{
			if(points[i][0]==points[i+1][0] && points[i][1]==points[i+1][1])//compare points
			{
				res = new int[2];
				res[0]=points[i][0];
				res[1]=points[i][1];
				i=points.length;//break loop since we found a match
			}
		}
		return res;
	}

	public static int[][] filterPointsByRange(double fromX, double toX,
			int[][] points) {
		int i;
		int j=-1;
		for(i=0;i<points.length && points[i][0]<=toX;i++)//loop through the point until we get out of range
		{
			if(points[i][0]>=fromX && j==-1)//remember the first point in range
			{
				j=i;
			}
		}
		i--;//compensate for the for loop adding 1 before check
		if(j==-1)//check if we didn't find anything in range 
			{
			j=i+1;
			}
		
		int[][] res = new int[i-j+1][2];//initialize the result array
		for(int k=0;k+j<=i;k++)
		{
			res[k]=points[k+j];
		}
		return res;
	}
		

	/******************** Task 3 ********************/
	public static int[][] findClosest(int[][] points) {
		int[][] res;
		int[][] pointsSortedByLex = sortByLex(points);
		int[] p = duplicates(pointsSortedByLex);
		if (p == null)
			res = findClosestRecursive(pointsSortedByLex);
		else {
			res = new int[1][];
			res[0] = p;
		}
		return res;
	}

	public static int[][] findClosestRecursive(int[][] points) {
		
		if (points==null)   					// stop condition for dealing with no points
			return null;
		if (points.length==1) 					// stop condition for dealing with 1 point
			return null;
		
		int[][] res = new int[2][];

		if (points.length<=4)					// stop condition for dealing with 2-4 points
			return findClosestSimple(points);
		
		int[][] pointsSortedbyLexLeft = new int[points.length/2][];                   // points.length > 4
		int[][] pointsSortedbyLexRight = new int[points.length-(points.length/2)][];  // points.length > 4
		for(int i=0;i<pointsSortedbyLexLeft.length;i++)
			pointsSortedbyLexLeft[i]=points[i];											//fill pointsSortedbyLexLeft with values from points in indexes 0 -> points.length/2-1
		for(int j=0;j<pointsSortedbyLexRight.length;j++)
			pointsSortedbyLexRight[j]=points[j+pointsSortedbyLexLeft.length];			//fill pointsSortedbyLexRight with values from points in indexes points.length/2 -> points.length-1
		
		int[][] closestPair1 = findClosestRecursive(pointsSortedbyLexLeft);		// find the closest pair at the left group of points
		int[][] closestPair2 = findClosestRecursive(pointsSortedbyLexRight);	// find the closest pair at the right group of points

		double d,d2;					//d,d2 - distances for closestPair1,closestPair2. d in the end will get the closest distances of all
		d = distance(closestPair1[0],closestPair1[1]);
		d2 = distance(closestPair2[0],closestPair2[1]);
		if (d>d2)
		{
			res=closestPair2;
			d=d2;
		}
		else
			res=closestPair1;
		
		int Mx = pointsSortedbyLexRight[0][0];

		
		int[][] middle = filterPointsByRange(Mx-d,Mx+d,points);				//middle=array with points in which x value: Mx-d <= points[][0] <= Mx+d
		middle = sortByY(middle);											//sort middle by middle[][1]
		
		for(int i=0;i<middle.length-1;i++)
			for(int j=i+1;j<middle.length && (middle[j][1]-middle[i][1])<d;j++)		// break when array end or distance on y line is bigger/equal then d - because d^2+d^2>d^2
				if(distance(middle[j],middle[i]) < d)								//if found 2 new closest points, save them at res
				{
					res[0]=middle[i];
					res[1]=middle[j];
					d=distance(middle[j],middle[i]);
				}
		return res;
	}

	

	/******************** Auxiliary functions ********************/

	/**
	 * @param arr
	 *          the input 2D array
	 * @return a string representation of a 2D array
	 */
	public static String matrixToString(int[][] arr) {
		String ret = "{ ";

		if (arr == null)
			ret = "null";
		else {
			for (int i = 0; i < arr.length; i++) {
				if (arr[i] != null) {
					ret += "{ ";
					for (int j = 0; j < arr[i].length; j++)
						ret += arr[i][j] + " ";
					ret += "} ";
				}
			}
			ret += "}";
		}

		return ret;
	}

	/**
	 * @param arr the input array
	 * @return a string representation of an array
	 */
	public static String arrayToString(int[] arr) {
		String ret = "{ ";

		if (arr == null)
			ret = "null";
		else {
			for (int i = 0; i < arr.length; i++)
				ret += arr[i] + " ";
			ret += "}";
		}

		return ret;
	}

	public static void main(String[] args) {

		// Test task 1
		int[][] test1in = { { 2, 9 }, { 2, 9 }, { 2, 6 }, { 8, 6 }, { 1, 2 },
				{ 1, 3 }, { 8, 9 }, { 0, 7 }, { 5, 9 }, { 9, 8 } };
		int[][] test1exp = { { 1, 2 }, { 1, 3 } };
		System.out.println("Test 1: expected=" + matrixToString(test1exp)
				+ " actual=" + matrixToString(findClosestSimple(test1in)));

		// Test task 2a
		int[][] test2in = { { 1, 2 }, { 0, 7 }, { 2, 9 }, { 2, 6 }, { 1, 3 } };
		int[][] test2exp = { { 0, 7 }, { 1, 2 }, { 1, 3 }, { 2, 6 }, { 2, 9 } };
		System.out.println("Test 2: expected=" + matrixToString(test2exp)
				+ " actual=" + matrixToString(sortByLex(test2in)));

		// Test task 2b
		int[][] test3in = { { 9, 8 }, { 5, 9 }, { 9, 5 }, { 8, 9 }, { 8, 6 } };
		int[][] test3exp1 = { { 9, 5 }, { 8, 6 }, { 9, 8 }, { 8, 9 }, { 5, 9 } };
		int[][] test3exp2 = { { 9, 5 }, { 8, 6 }, { 9, 8 }, { 5, 9 }, { 8, 9 } };
		System.out.println("Test 3: expected=" + matrixToString(test3exp1) + " or "
				+ matrixToString(test3exp2) + " actual="
				+ matrixToString(sortByY(test3in)));

		// Test task 2c
		int[][] test4in = { { 0, 7 }, { 1, 2 }, { 1, 3 }, { 2, 6 }, { 2, 9 } };
		int[] test4exp = null;
		System.out.println("Test 4: expected=" + arrayToString(test4exp)
				+ " actual=" + arrayToString(duplicates(test4in)));

		int[][] test5in = { { 0, 7 }, { 1, 2 }, { 1, 2 }, { 2, 6 }, { 2, 6 } };
		int[] test5exp1 = { 1, 2 };
		int[] test5exp2 = { 2, 6 };
		System.out.println("Test 5: expected=" + arrayToString(test5exp1) + " or "
				+ arrayToString(test5exp2) + " actual="
				+ arrayToString(duplicates(test5in)));

		// Test task 2d
		int[][] test6in = { { 3, 0 }, { 3, 5 }, { 4, 3 }, { 6, 4 }, { 7, 3 } };
		int[][] test6exp = { { 3, 0 }, { 3, 5 }, { 4, 3 } };
		System.out.println("Test 6: expected=" + matrixToString(test6exp)
				+ " actual=" + matrixToString(filterPointsByRange(8, 8, test6in)));

		// Test task 3
		 int[][] test7in = {{0,7},{1,2},{1,3},{2,6},{2,9}};
		 int[][] test7exp = {{1,2},{1,3}};
		 System.out.println("Test 7: expected=" + matrixToString(test7exp) +
		 " actual=" + matrixToString(findClosestRecursive(test7in)));

		// Test task 3
		int[][] test8in = { { 9, 5 }, { 2, 9 }, { 2, 6 }, { 8, 6 }, { 1, 2 },
				{ 1, 3 }, { 8, 9 }, { 0, 7 }, { 5, 9 }, { 9, 8 } };
		int[][] test8exp = { { 1, 2 }, { 1, 3 } };
		System.out.println("Test 8: expected=" + matrixToString(test8exp)
				+ " actual=" + matrixToString(findClosest(test8in)));

	}
}
